package org.yh.leetcode;

import java.util.ArrayList;

/**
 * @Author: yh
 * @Description:
 * @Date: Created in 13:39 2019/5/13
 * @Modified By:
 */
public class Test4 {

    //编写一个函数来查找字符串数组中的最长公共前缀。
    //如果不存在公共前缀，返回空字符串 ""。
    public String longestCommonPrefix(String[] strs) {
        //思路：最长公共前缀 ，最长只能为数组里最短的那个支付串。
        // 1.先找出最短字符串.
        // 2.循环比较：循环最短字符串的长度，和其他字符串比较每个字符是否相等，直到有一个不等则返回前面所有相等的字符
        String prefix = "";
        if (strs.length == 0) {
            return prefix;
        }
        String min = strs[0];
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < min.length()) {
                min = strs[i];
            }
        }
        int x = 0;
        boolean flag = false;
        for (int i = 0; i < min.length(); i++) {
            for (int j = 0; j < strs.length - 1; j++) {
                char current = strs[j].charAt(i);
                char next = strs[j + 1].charAt(i);
                //如果当前值不等于下一个值，改变flag
                if (current != next) {
                    flag = true;
                }
            }
            //终止循环
            if (flag) {
                break;
            }
            x++;
        }
        return strs[0].substring(0, x);
    }


    public static void main(String[] args) {
        Test4 t4 = new Test4();
        String strs[] = {"dog", "doracecar", "docar"};
        String s = t4.longestCommonPrefix(strs);
        System.out.println("最长前缀：" + s);

    }
}
